package com.leo.basic.chapter01;

/**
 * 递归复习
 *      题目：斐波那契数列；汉诺塔；逆序输出正整数的各位数；排列组合递归写法
 *      递归：巧妙的保存了数据的状态信息！！！
 *          分解问题，归纳问题是核心
 *          一般都可以写出 递归式 的！
 * @author xuexiaolei
 * @version 2017年11月30日
 */
public class P01Recursion {
    /**
     * 斐波那契数列的递归写法
     *      核心：一个小的解决终点，然后大的问题可以循环在小问题上解决
     * @param n
     * @return
     */
    long F(int n){
        if (n<=1) return n;
        return F(n-1)+F(n-2);
    }

    /**
     * 斐波那契数列的递推写法
     * @param n
     * @return
     */
    long F1(int n){
        if (n<=1) return n;
        long fn = 0;
        long fn_1 = 1;
        long fn_2 = 0;
        for (int i = 2; i <= n; i++) {
            fn = fn_1 + fn_2;
            fn_2 = fn_1;
            fn_1 = fn;
        }
        return fn;
    }

    long j(int n){
        if (n <=1) return 1;
        return j(n-1)*n;
    }

    /**
     * 倒序输出正整数的各位数
     * @param n
     */
    void printDigit(int n){
        System.out.print(n%10);
        if (n >= 10){
            printDigit(n/10);
        }
    }

    /**
     * 汉诺塔
     *      有柱子 x z y，最终将x上的n个圆盘借助z移动到y上
     *      递归思想：
     *          1.将x上的n-1个放入到z上，借助y
     *          2.将x上的n圆盘放到y上
     *          3.将z上的n-1个圆盘放入y
     * @param n
     * @param from
     * @param tmp
     * @param to
     */
    void hanoi(int n,char from,char tmp,char to){
        if (n>0) {
            hanoi(n - 1, from, to, tmp);
            System.out.println("take " + n + " from " + from + " to " + to);
            hanoi(n - 1, tmp, from, to);
        }
    }

    /**
     * 产生排列的递归写法
     * @param t     数组
     * @param k     起始排列值
     * @param n     数组长度
     */
    void pai(int[] t, int k, int n){
        if (k == n-1){//输出这个排列
            for (int i = 0; i < n; i++) {
                System.out.print(t[i] + " ");
            }
            System.out.println();
        }else {
            for (int i = k; i < n; i++) {
                int tmp = t[i]; t[i] = t[k]; t[k] = tmp;//一次挑选n个字母中的一个,和前位置替换
                pai(t, k+1, n);                      //再对其余的n-1个字母一次挑选
                tmp = t[i]; t[i] = t[k]; t[k] = tmp;    //再换回来
            }
        }
    }

    /**
     * 组合的递归写法
     * @param chars
     * @param contains
     * @param k
     */
    private void zuhe(char[] chars, boolean[] contains, int k){
        if (k == chars.length){
            for (int i = 0; i < chars.length; i++) {
                if (contains[i]) System.out.print(chars[i]);
            }
            System.out.println("]");
        }else {
            contains[k]=true;
            zuhe(chars, contains, k+1);
            contains[k]=false;
            zuhe(chars, contains, k+1);
        }
    }

    public void zuhe(String s){
        zuhe(s.toCharArray(), new boolean[s.length()], 0);
    }

    public static void main(String[] args) {
        P01Recursion t = new P01Recursion();
        t.printDigit(12345);
        System.out.println();
        t.printDigit(10);
        System.out.println();
        t.printDigit(0);
        System.out.println();
        t.hanoi(5, 'X', 'Z','Y');
        t.pai(new int[]{0,1,2,3,4}, 0, 5);
        t.zuhe("abc");
    }
}
